package com.love.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort {

    // 可以设置进制，不一定10进制，随你设置
    public static int BASE = 10;

    public static int MAXN = 50001;

    public static int[] help = new int[MAXN];

    public static int[] cnts = new int[BASE];




    public static int[] sortArray(int[] arr){
        if(arr.length > 1){
            // 如果会溢出，那么要改用 long 类型数组来排序
            int n = arr.length;
            // 找到数组中的最小值
            int min = arr[0];
            for (int i = 1; i < n; i++){
                min = Math.min(min,arr[i]);
            }
            int max = 0;
            for (int i = 0; i < n; i++){
                // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
                arr[i] -= min;
                // 记录数组中的最大值
                max = Math.max(max,arr[i]);
            }
            // 根据最大值在BASE机制下的位数
            radixSort(arr,n,bits(max));
            // 数组中所有数都减去了最小值，所以最后不要忘了还原
            for (int i = 0; i < n; i++) {
                arr[i] += min;
            }
        }
        return arr;
    }



    // 返回 number 在 BASE进制下有几位
    public static int bits(int number){
        int ans = 0;
        while (number > 0){
            ans++;
            number /= BASE;
        }
        return ans;
    }




    /**
     * 词频统计一般有两种方法
     * 1）map
     * 2)数组 ： index -> 表示数字 ,value -> 词频，例 arr[1] = 3,表示 数字1 出现了 3 次
     *
     * 基数排序的核心代码
     * @param arr ： arr内要保证没有负数
     * @param n ： arr的长度
     * @param bits ： 是arr中最值在BASE进制下有几位
     */
    public static void radixSort(int[] arr,int n,int bits){
        // 理解的时候可以假设 BASE = 10
        for(int offset = 1; bits > 0; offset *= BASE,bits--){
            Arrays.fill(cnts,0);
            for (int i = 0; i < n; i++){
                // 数字提取某一位的技巧
                cnts[(arr[i] / offset) % BASE]++;
            }
            // 这一步很牛，处理成前缀数累加的形式
            for (int i = 1; i < BASE ; i++) {
                cnts[i] = cnts[i] + cnts[i - 1];
            }

            for(int i = n - 1; i >= 0; i-- ){
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
            }
            for (int i = 0; i < n; i++){
                arr[i] = help[i];
            }
        }

    }



}
